By

文章目录
  1. 1. 堆排序 (Heap Sort)
    1. 1.1. 最大堆的向下调整算法分析

（这篇文章是2006年我发布在博客园上面的，想想已经八年有余。今天好不容易找到了，挪到这里，收藏一下吧。）

堆排序 (Heap Sort)

堆排序分为两个步骤：

  • 第一步，根据初始输入数据，利用堆的调整算法形成初始堆。
  • 第二步，通过一系列的记录交换和重新调整堆进行排序。

最大堆的向下调整算法分析

调用了O(n)次Adjust()算法，堆排序的时间复杂性为O(nlog2n)。

该算法的附加存储主要是执行记录交换时所用的一个临时记录。
因此，该算法的空间复杂性为O(1)。

堆排序是一个不稳定的排序方法。

基于C的实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>

void swap(int &x, int &y)
{
    int temp = x;
    x = y;
    y = temp;
}

void Adjust(int *a, int parent, int high)
{
    int l = 2 * parent + 1;
    int r = l + 1;
    int flag = parent;

    if (l<=high && a[l]>a[flag]) {
        flag = l;
    }
    if (r<=high && a[r]>a[flag]) {
        flag = r;
    }
    if (flag != parent) {
        swap(a[parent], a[flag]);
        Adjust(a, flag, high);
    }
}

void HeapSort(int *a, int n)
{
    int i;

    for (i=n-1; i>=0; i--) {
        Adjust(a, i, n - 1);
    }
    for (i=n-1; i>=0; i--) {
        swap(a[0], a[i]);
        Adjust(a, 0, i - 1);
    }
}

void Output(int *a, int n)
{
    int i;

    for (i=0; i<n; i++) {
        printf("\t%d", a[i]);
    }
    printf("\n");
}

int main()
{
    int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
    int n = 8;

    Output(a, n);
    HeapSort(a, n);
    Output(a, n);

    return 0;
}

/*
        49      38      65      97      76      13      27      49
        13      27      38      49      49      65      76      97
Press any key to continue
*/

(END)

文章目录
  1. 1. 堆排序 (Heap Sort)
    1. 1.1. 最大堆的向下调整算法分析